#include "mySearch.h"
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <stack>

using namespace std;
SSTable::SSTable()
{
	length = 0;
	origin = NULL;
}

SSTable::SSTable(int length, int *origin)
{
	this->length = length;
	this->origin = origin;
}

SSTable::~SSTable()
{
}

int SSTable::getLength()
{
	return length;
}

int *SSTable::getOrigin()
{
	return origin;
}

void SSTable::setLength(int length)
{
	this->length = length;
}

void SSTable::setOrigin(int *origin)
{
	this->origin = origin;
}

int SSTable::binSearch(int val)
{
	int low = 0;
	int high = length;
	int result;
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (origin[mid] == val)
		{
			result = mid;
			break;
		}
		else if (origin[mid] > val)
			high = mid - 1;
		else
			low = mid + 1;
	}
	if (low > high)
		result = -1;
	return result;
}

BSTreeNode::BSTreeNode()
{
	data = 0;
	lchild = NULL;
	rchild = 0;
}

BSTreeNode::BSTreeNode(int data)
{
	this->data = data;
}

BSTreeNode::BSTreeNode(int data, BSTreeNode *lchild, BSTreeNode *rchild)
{
	this->data = data;
	this->lchild = lchild;
	this->rchild = rchild;
}

BSTreeNode::~BSTreeNode()
{
}

int BSTreeNode::getData()
{
	return data;
}

BSTreeNode *BSTreeNode::getLChild()
{
	return lchild;
}

BSTreeNode *BSTreeNode::getRChild()
{
	return rchild;
}

void BSTreeNode::setData(int data)
{
	this->data = data;
}

void BSTreeNode::setLChild(BSTreeNode *lchild)
{
	this->lchild = lchild;
}

void BSTreeNode::setRChild(BSTreeNode *rchild)
{
	this->rchild = rchild;
}

BSTree::BSTree()
{
	num = 0;
	root = NULL;
}

BSTree::BSTree(int num, int *data)
{
	this->num = num;
	root->setData(data[0]);
	BSTreeNode *k = new BSTreeNode; 
	for (int i = 1; i < num; i++)
	{
		BSTreeNode *newroot = new BSTreeNode;
		newroot = root;
		while (newroot != NULL)
		{
			if (newroot->getData() > data[i])
			{
				k = newroot;
				newroot = newroot->getLChild();
			}
			else if (newroot->getData() < data[i])
			{
				k = newroot;
				newroot = newroot->getRChild();
			}
		}
		if (k->getData() > data[i])
		{
			BSTreeNode *newroot2 = new BSTreeNode;
			newroot2->setData(data[i]);
			k->setLChild(newroot2);
		}
		else
		{
			BSTreeNode *newroot2 = new BSTreeNode;
			newroot2->setData(data[i]);
			k->setRChild(newroot2);
		}
	}
}
BSTree::~BSTree()
{
}

int BSTree::getNum()
{
	return num;
}

BSTreeNode *BSTree::getRoot()
{
	return root;
}

void BSTree::setNum(int num)
{
	this->num = num;
}

void BSTree::setRoot(BSTreeNode *root)
{
	this->root = root;
}

void printTemp(BSTreeNode *root, string &result)
{
}

string BSTree::printTree()
{
	if (root == NULL)
		return "\0";
	BSTreeNode *newroot = new BSTreeNode;
	stack<BSTreeNode *> q;
	newroot = root;
	string s;
	while ((!q.empty()) || (newroot != NULL))
	{
		while (newroot != NULL)
		{
			if (newroot->getData() >= 0)
			{
				s += char(newroot->getData() + 48);
			}
			else
			{
				s+='-';
				s+=char(-(newroot->getData())+48);
			}
			s += " ";
			q.push(newroot);
			newroot = newroot->getLChild();
		}
		if (!q.empty())
		{
			newroot = q.top();
			q.pop();
			newroot = newroot->getRChild();
		}
	}
	return s;
}

bool BSTree::searchNode(int val)
{
	BSTreeNode *newroot = new BSTreeNode;
	newroot = root;
	while (newroot != NULL)
	{
		if (newroot->getData() == val)
			return 1;
		else if (newroot->getData() > val)
		{
			newroot = newroot->getLChild();
		}
		else if (newroot->getData() < val)
		{
			newroot = newroot->getRChild();
		}
	}
	if (newroot == NULL)
		return 0;
	return 0;
}

bool BSTree::addNode(int val)
{
	BSTreeNode *k = new BSTreeNode;
	BSTreeNode *newroot = new BSTreeNode;
	newroot = root;
	while (newroot != NULL)
	{
		if (newroot->getData() == val)
			return 0;
		else if (newroot->getData() > val)
		{
			k = newroot;
			newroot = newroot->getLChild();
		}
		else if (newroot->getData() < val)
		{
			k = newroot;
			newroot = newroot->getRChild();
		}
	}
	if (k->getData() > val)
	{
		BSTreeNode *newroot2 = new BSTreeNode;
		newroot2->setData(val);
		k->setLChild(newroot2);
		return 1;
	}
	else
	{
		BSTreeNode *newroot2 = new BSTreeNode;
		newroot2->setData(val);
		k->setRChild(newroot2);
		return 1;
	}
}

bool BSTree::deleteNode(int val)
{
	BSTreeNode *k = new BSTreeNode;		  
	BSTreeNode *newroot = new BSTreeNode; 
	newroot = root;
	k = newroot;
	while (newroot != NULL)
	{
		if (newroot->getData() == val)
		{
			if (newroot->getLChild() == NULL && newroot->getRChild() == NULL)
			{
				if (k->getData() > val)
				{
					delete newroot;
					k->setLChild(NULL);
					return 1;
				}
				else
				{
					delete newroot;
					k->setRChild(NULL);
					return 1;
				}
			}
			else if (newroot->getLChild() != NULL && newroot->getRChild() == NULL)
			{
				if (k->getData() > val)
				{
					k->setLChild(newroot->getLChild());
					delete newroot;
					return 1;
				}
				else
				{
					k->setRChild(newroot->getLChild());
					delete newroot;
					return 1;
				}
			}
			else if (newroot->getLChild() == NULL && newroot->getRChild() != NULL)
			{
				if (k->getData() > val)
				{
					k->setLChild(newroot->getRChild());
					delete newroot;
					return 1;
				}
				else
				{
					k->setRChild(newroot->getRChild());
					delete newroot;
					return 1;
				}
			}
			else if (newroot->getLChild() != NULL && newroot->getRChild() != NULL)
			{
				BSTreeNode *q = new BSTreeNode;
				BSTreeNode *s = new BSTreeNode;
				q = newroot;
				s = newroot->getLChild();
				while (s->getRChild() != NULL)
				{
					q = s;
					s = s->getRChild();
				}
				newroot->setData(s->getData());
				if (q != newroot)
					q->setRChild(s->getLChild());
				else
					q->setLChild(s->getLChild());
				delete s;
				return 1;
			}
		}
		else if (newroot->getData() > val)
		{
			k = newroot;
			newroot = newroot->getLChild();
		}
		else if (newroot->getData() < val)
		{
			k = newroot;
			newroot = newroot->getRChild();
		}
	}
	if (newroot == NULL)
		return 0;
	return 0;
}
